package com.cat.dynamicPlanning;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/generate-parentheses/?envType=problem-list-v2&envId=dynamic-programming&
 * @create 2025/9/8 10:06
 * @since JDK17
 */

public class Solution95 {
    List<String> ans = new ArrayList<>();
    int n, k;
    char[] s;
    void dfs(int cur, int l, int r) {
        if (cur == n) {
            ans.add(new String(s));
            return;
        }
        if (l < k) {
            s[cur] = '(';
            dfs(cur + 1, l + 1, r);
        }
        if (r < k && r < l) {
            s[cur] = ')';
            dfs(cur + 1, l, r + 1);
        }
    }

    public List<String> generateParenthesis(int n) {
        k = n;
        this.n = n * 2;
        s = new char[n * 2];
        dfs(0, 0, 0);
        return ans;
    }
}
